#include "StdAfx.h"
#include "ASTDiffVisitor.h"
#include "ASTNode.h"
//#include "ASTree.h"

namespace AST {

DiffVisitor::DiffVisitor(void)
{
	vMode = DiffVisitor::VISIT_ONLY;
}

DiffVisitor::DiffVisitor(VisitMode mode, NodeMatchesMap* mapForMatches, std::set<Node*>* changeSet) : vMode(mode),
																									  matchingNodesMap(mapForMatches),
																									  changedFunctionsAndMethods(changeSet){
}

DiffVisitor::~DiffVisitor(void)
{
}

DiffVisitor::VisitMode DiffVisitor::mode (void) const  {
	return vMode;
}

void DiffVisitor::discover_vertex(vertexDesc v, const Graph & g) {
	if (mode()==PROPAGATE_CHANGES)
		return;

	fprintf(stderr, "Discovered node: %s\n", g[v].vertexName.c_str());
	// this can probably all be moved to the finish_vertex event, which should be triggered inmediatelly after this event.
	Graph* deconstGraph = const_cast<Graph*>(&g); //we WILL modify the graph
	Node* node = (*deconstGraph)[v].nodeObject;

	NodeMatchesMap::iterator iter;//iterator to explore nodeMatches map
	vertexDesc& parentVertex = (*deconstGraph)[v].matchInfo.parent;
	//Treat leaves specially. Inner-node matching mostly cares about leaf matches
	//should it really do this for VISIT_ONLY?
	if (node->leaf()){
		(*deconstGraph)[parentVertex].matchInfo.leaves++;  //update parent's  leaf count
		//if leaf is matched
		if ((iter = node->tree->nodeMatches.find(node)) != node->tree->nodeMatches.end()){
			fprintf(stderr, "	Matches %s\n", iter->second.matchingNode->nodeName.c_str()); 
			//update this vertex match info
			(*deconstGraph)[v].matchInfo.matched = true;
			(*deconstGraph)[v].matchInfo.matchedLeaves[node] = iter->second;
			(*deconstGraph)[v].matchInfo.sim = iter->second.sim;
			(*deconstGraph)[v].matchInfo.matchingNode = iter->second.matchingNode;
			//update parent vertex match info
			(*deconstGraph)[parentVertex].matchInfo.matchedLeaves[node] = iter->second;
			//update other node's info
			Graph* otherGraph = iter->second.matchingNode->tree->treeGraph();
			(*otherGraph)[iter->second.matchingNode->getVertex()].matchInfo.matched = true;
			(*otherGraph)[iter->second.matchingNode->getVertex()].matchInfo.matchingNode = node;
			(*otherGraph)[iter->second.matchingNode->getVertex()].matchInfo.sim = iter->second.sim;
		}
	}
	else {//inner node
			//nothing to do if just discovering (?)
	}
}

void DiffVisitor::initialize_vertex(vertexDesc v, const Graph & g){
	if (mode()!=PROPAGATE_CHANGES){
		Graph* deconstGraph = const_cast<Graph*>(&g); //we WILL modify the graph
		fprintf(stderr, "Initializing node: %s:\n", g[v].vertexName.c_str());
		(*deconstGraph)[v].matchInfo.leaves=0;
		(*deconstGraph)[v].matchInfo.matchedLeaves.clear();
		(*deconstGraph)[v].matchInfo.first=false;
		(*deconstGraph)[v].matchInfo.sim=0;
		(*deconstGraph)[v].matchInfo.matched=false;
		(*deconstGraph)[v].matchInfo.someChange=false;
	}
}

void DiffVisitor::tree_edge(edgeDesc e, const Graph & g){
	Graph* deconstGraph = const_cast<Graph*>(&g);
	fprintf(stderr, "tree edge event: %s->%s\n", g[e.m_source].vertexName.c_str(),g[e.m_target].vertexName.c_str());
	//record parent
	(*deconstGraph)[e.m_target].matchInfo.parent= e.m_source;
}

void DiffVisitor::finish_vertex(vertexDesc thisVertex, const Graph & g){
	Graph* deconstGraph = const_cast<Graph*>(&g);
	fprintf(stderr, "finished vertex event: %s with %d/%d matched leaves\n",	g[thisVertex].vertexName.c_str(), 
																				g[thisVertex].matchInfo.matchedLeaves.size(),
																				g[thisVertex].matchInfo.leaves);
	//if in diffing mode, and not a leaf check our leaf match map against second tree's leaf match map
	if (vMode == VISIT_AND_MATCH_INNER && !(g[thisVertex].nodeObject->leaf())){

	
		//try to avoid work, ignore node if our map is empty
		if (g[thisVertex].matchInfo.matchedLeaves.empty()){
			goto done_with_inner_node;
		}

		//some useful shorthands
		Graph* otherGraph = ((*deconstGraph)[thisVertex].matchInfo.matchedLeaves).begin()->second.matchingNode->tree->treeGraph();
		//maybe recurse tree up to root, if root is hit with no matches, then there is nothing else to look for
//		vertexDesc &otherGraphVertex = (*deconstGraph)[thisVertex].matchInfo.matchedLeaves.begin()->second->getVertex();
		NodeMatchesMap& thisNodeLeafMatchMap = (*deconstGraph)[thisVertex].matchInfo.matchedLeaves;
		
		bool match = false;
		float match2coef = 0;
		std::set<Node *> visited;
		NodeMatchesMap::iterator leftOverIterator;
		unsigned int leaves = (*deconstGraph)[thisVertex].matchInfo.leaves;
		//for every leaf of this node
		for(NodeMatchesMap::iterator iter = thisNodeLeafMatchMap.begin(); iter!= thisNodeLeafMatchMap.end(); iter++){
	
			vertexDesc nextInnerVertex = iter->second.matchingNode->getVertex();
			 
			//ask it's matching leaf on the other tree about its parent, if it matches, great
			//if it does not, add that node to the list of visited nodes,
			//recurse up to the root or until an already-visited node is found (done)
			do {
				nextInnerVertex = (*otherGraph)[nextInnerVertex].matchInfo.parent;
				//check if node in other graph is already matched, if so, continue up
				if ((*otherGraph)[nextInnerVertex].matchInfo.matched)
					continue;
				
				//add other node to visited list 
				visited.insert((*otherGraph)[nextInnerVertex].nodeObject);

				unsigned int matchingLeaves=1;
				NodeMatchesMap& otherNodeMatchMap = (*otherGraph)[nextInnerVertex].matchInfo.matchedLeaves;
				leftOverIterator = iter; //start with the next leaf in the map
				while ( ++leftOverIterator != thisNodeLeafMatchMap.end()){
					//if the other map contains the leaf this leaf matches
					if (otherNodeMatchMap.find(leftOverIterator->second.matchingNode) != otherNodeMatchMap.end()){
						matchingLeaves++;
					}
				}
				// compute match2 coefficient
				// |common(x,y)|/max(|x|,|y|)
				//matching results for t = 0.6 if n> 4 and t = 4 if n <= 4
				//where n is the number of leaves inthe sub-tree
				//TODO: precompute as much as possible. Precompute this vertex's leaves
				unsigned int maxLeaves = std::max(leaves, (*otherGraph)[nextInnerVertex].matchInfo.leaves);
				match2coef = ((float)matchingLeaves)/maxLeaves;
				if (match2coef >= ((maxLeaves>4)?0.6f:0.2f)){ //dynamic weighing based on sub-tree size
					//match found
					//record it in global match info map
					Match matchNodeInfo;
					matchNodeInfo.matchingNode = (*otherGraph)[nextInnerVertex].nodeObject;
					matchNodeInfo.sim= match2coef;
					(*matchingNodesMap)[(*deconstGraph)[thisVertex].nodeObject] = matchNodeInfo;
					
					//mark the node on the other tree as matched
					(*otherGraph)[nextInnerVertex].matchInfo.matched = true;
					(*otherGraph)[nextInnerVertex].matchInfo.sim=match2coef;
					(*otherGraph)[nextInnerVertex].matchInfo.matchingNode=(*deconstGraph)[thisVertex].nodeObject;
					
					//mark this node as matched
					match =true;
					(*deconstGraph)[thisVertex].matchInfo.matched =true;
					(*deconstGraph)[thisVertex].matchInfo.sim = match2coef;
					(*deconstGraph)[thisVertex].matchInfo.matchingNode = (*otherGraph)[nextInnerVertex].nodeObject;

					//get out of here
					break; //exit while loop
				}
			}while (!((*otherGraph)[nextInnerVertex].matchInfo.first)); //OUCH! this only works if first node in DFS traversal is also the rroot of the tree

			if (match)
				break; //exit for
		}

		//create second tree's iterator here, start with a node that we match
		//VertexIterator const iter =  otherGraph[
		// pick an unmatched node form second tree
		//it would be more efficient to have a list of those, and remove them as they get matched
		//for now we are just going to iterate over all nodes in the second tree
		// pick leaves in order until one matches
		//maybe take into account weighting
		//evaluate match against inner nodes of second tree here
		//use an iterator on the edges of the second tree
		//assume that things will be found in almost the same order
		//keep iterator as global, keep incrementing until match is found, or point back around to the begining until the original position of
		// the iterator is reached once again (no inner node of second tree was good enough), no match is found
		//need to keep track of which leaves I have? I think so because I need to see if they match the leaves of the candidate inner node 
		//on the second tree
	}
	done_with_inner_node:
	
	if(!(g[thisVertex].matchInfo).first){ //if not the root vertex
		//this got crazy, rewrote in simple terms, but need definitions below:
		Node* thisNode = g[thisVertex].nodeObject;
		vertexDesc& parentVertex = (*deconstGraph)[thisVertex].matchInfo.parent;	
		if (mode() !=PROPAGATE_CHANGES){
			//update parents # of leaves
			(*deconstGraph)[g[thisVertex].matchInfo.parent].matchInfo.leaves+= g[thisVertex].matchInfo.leaves;
			//update parents # matched leafs
			//now update parent's leaf match map, by copying the map
			(*deconstGraph)[parentVertex].matchInfo.matchedLeaves.insert	(g[thisVertex].matchInfo.matchedLeaves.begin(),
																				g[thisVertex].matchInfo.matchedLeaves.end());
		}
		//set own change flag and propagate upward
		if (mode() != VISIT_ONLY){
			if (((*deconstGraph)[thisVertex].matchInfo.sim<1) || ((*deconstGraph)[thisVertex].matchInfo.someChange)){
				(*deconstGraph)[parentVertex].matchInfo.someChange = true;
				(*deconstGraph)[thisVertex].matchInfo.someChange = true;
				CXCursorKind kind = clang_getCursorKind(thisNode->cursor);
				//if this is one of the kinds we care about, add it to the list
				if (kind == CXCursor_Constructor || kind == CXCursor_FunctionDecl  || kind == CXCursor_CXXMethod || kind == CXCursor_FunctionDecl)
					changedFunctionsAndMethods->insert(thisNode);
			}
		}
	}
}

void DiffVisitor::start_vertex(vertexDesc v, const Graph & g){
	Graph* deconstGraph = const_cast<Graph*>(&g);
	fprintf(stderr, "first vertex\n");
	(*deconstGraph)[v].matchInfo.first=true;

}

//should not be called. Implies a cycle. 
void DiffVisitor::back_edge(edgeDesc e, const Graph & g){
	fprintf(stderr, "back edge event: %s->%s\n", g[e.m_source].vertexName.c_str(),g[e.m_target].vertexName.c_str());
	fprintf(stderr, "how was this called?\n"); 
	//ASSERT here
}

//should not be called. Implies more than one parent.
void DiffVisitor::forward_or_cross_edge(edgeDesc e, const Graph & g){
	fprintf(stderr, "forward edge event: %s->%s\n", g[e.m_source].vertexName.c_str(),g[e.m_target].vertexName.c_str());
	fprintf(stderr, "how was this called?\n"); 
	//ASSERT here
}


}//namespace AST
